package dp;

import java.util.Arrays;

public class ChangeMakingProblem2 {
    //零钱兑换 有多少种兑换方法 动态规划
    public static void main(String[] args) {
        coinChange(new int[]{1, 2, 5}, 5);
    }

    private static void coinChange(int[] ints, int acount) {
        int[][] dp = new int[ints.length][acount + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][0] = 1;
                dp[0][j] = 1;
            }
        }

        for (int i = 1; i < ints.length; i++) {
            int anInt = ints[i];
            for (int j = 1; j < acount + 1; j++) {
                if (j >= anInt) { //放得下
                    dp[i][j] = dp[i - 1][j] + dp[i][j - anInt];
                } else { //放不下
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }


        print(dp);
    }

    private static void print(int[][] dp) {
        System.out.println("=====");
        for (int[] ints : dp) {
            System.out.println(Arrays.toString(ints));
        }
        System.out.println("=====");
    }
}
